// 关键路径
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"

int earliest[MAX] = {0};
int lastest[MAX] = {0};
int spare[MAX] = {0};
void Critical_Path(Adj_Matrix G, int s)
{
	int que[MAX];
	int f, r;
	f = r = 0;
	que[r++] = s;
	// 1.求活动最早开始时间
	// 从q点到w：
	// earliest[w] = max(earliest[w],G.M[q][w] + earliest[q])
	earliest[s] = 0;
	while (f < r)
	{
		int q = que[f++];
		for (int w = 0; w < G.node_num; w++)
		{
			if (G.M[q][w] != 0 && G.M[q][w] != INFINITY)
			{
				que[r++] = w;
				if (G.M[q][w] + earliest[q] > earliest[w])
				{
					earliest[w] = G.M[q][w] + earliest[q];
				}
			}
		}
	}

	int p = que[f - 1];							//队列最后一个节点即为出度为0的点
	printf("Earliset_time:%3d\n", earliest[p]); //输出工程最早完成时间

	// 2.求活动开始最晚时间  逆拓扑排序
	// lastest[] 初始化为 INFINITY
	// 从q 到 w 的最晚完成时间：
	// lastest[w]=min(lastest[w],lastest[q] - G.M[w][q])
	// 解释：假如存在w1 --> q,w2 --> q,w3 --> q ...    lastest[wi]就是lastest[q] - G.M[wi][q]
	//      但是如果存在 w-->q1 ,w-->q2 ,...    lastest[w]就是lastest[qi] - G.M[w][qi]中对小的一个
	for (int i = 0; i < MAX; i++)
	{
		lastest[i] = INFINITY;
		spare[i] = INFINITY;
	}
	lastest[p] = earliest[p];
	f = r = 0;
	que[r++] = p;
	while (f < r)
	{
		int q = que[f++];
		for (int w = 0; w < G.node_num; w++)
		{
			// 注意这是G.M[w][q] 表示从 w --> p 图的逆置
			if (G.M[w][q] != 0 && G.M[w][q] != INFINITY)
			{
				que[r++] = w;
				if (lastest[q] - G.M[w][q] < lastest[w])
					lastest[w] = lastest[q] - G.M[w][q];
			}
		}
	}
	// lastest[]==earliest[] 该节点就是关键节点

	// 3.输出所有关键路径
	int stack[MAX];
	int top = -1;
	stack[++top] = s;
	int k = -1; //节点标记
	while (top >= 0)
	{
		int n = stack[top];
		if (n == p) //找到终点节点就输出
		{

			printf("Critical_Path:");
			for (int i = 0; i <= top; i++)
			{
				printf("%3d", stack[i]);
			}
			printf("\n");
		}
		int w = ++k;  //w作为当前邻接点开始的节点
		int flag = 0; //标记，若有节点入栈，flag=1，否则就是邻接点遍历了一遍也没有符合的节点，需要退栈了
		for (; w < G.node_num; w++)
		{
			if (G.M[n][w] != 0 && G.M[n][w] != INFINITY)
			{
				if (lastest[w] == earliest[w])
				{
					stack[++top] = w;
					k = -1; //k恢复为-1 表示下一个节点依旧从0号节点开始遍历
					flag = 1;
					break;
				}
			}
		}
		if (!flag) //n的邻接点都找过了，这一轮没有节点入栈
		{
			k = stack[top]; //k为当前栈顶，是次栈顶的邻接点 下一次遍历从这个节点开始
			top--;
		}
	}
}

int main()
{
	/*******************code*******************/
	Adj_Matrix G;
	creat_critical(G);
	// 1.找到入度为0的节点作为起始点
	int degree[MAX] = {0};
	for (int i = 0; i < G.node_num; i++)
	{
		for (int j = 0; j < G.node_num; j++)
		{
			if (G.M[j][i] != 0 && G.M[j][i] != INFINITY)
			{
				degree[i]++;
			}
		}
	}
	// 对度为0的顶点求关键路径  一般只有一个入度为0的节点
	for (int i = 0; i < G.node_num; i++)
	{
		if (!degree[i])
		{
			Critical_Path(G, i);
		}
	}
	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
